package com.fwpsl.graph.shortestpath.singlesource;

import com.fwpsl.graph.Edge;
import com.fwpsl.graph.Graph;
import com.fwpsl.graph.Vertex;

import java.util.*;

import static com.fwpsl.graph.shortestpath.singlesource.AbstractSingleSource.PathNode.PATH_NODE_TYPE_SINGLE;

/**
 * @author: 风戏fw
 * @date: 2024/4/14
 * @description: SPFA（Shortest Path Faster Algorithm）是一种用于解决带权有向图中单源最短路径问题的算法。
 * 它是Bellman-Ford算法的改进版，使用队列优化，可以在稀疏图中比Bellman-Ford算法更快。
 */
public class SPFA<T> extends AbstractSingleSource<T> {

    /**
     * SPFA算法
     * <p>
     * 如果存在负权重的环，SPFA算法可能会陷入无限循环。
     * 解决方案，记录每个顶点的出度数，当出度数 >= 顶点数时，必然有环，而且一定是负权重环。todo 需要时再实现
     *
     * @param graph
     * @param start
     * @return
     */
    @Override
    public Map<Vertex<T>, PathNode> singlePathList(Graph<T> graph, Vertex<T> start) {
        // 距离数组
        Map<Vertex<T>, PathNode> distMap = new HashMap<>();
        for (Vertex<T> vertex : graph.getVertices()) {
            distMap.put(vertex, new PathNode(vertex, INF, PATH_NODE_TYPE_SINGLE));
        }
        distMap.get(start).distance = 0;

        // 队列, inQueueMap用于优化‘判断当前的点是否已经加入到队列’逻辑
        Queue<Vertex<T>> queue = new LinkedList<>();
        Map<Vertex<T>, Boolean> inQueueMap = new HashMap<>();
        queue.offer(start);
        inQueueMap.put(start, Boolean.TRUE);
        while (!queue.isEmpty()) {
            Vertex<T> currentVertex = queue.poll();
            inQueueMap.put(start, Boolean.FALSE);

            for (Edge<T> edge : currentVertex.getEdges()) {
                Vertex<T> source = edge.getSource();
                Vertex<T> destination = edge.getDestination();
                Double newDist;
                if ((newDist = distMap.get(source).distance + edge.getWeight()) < distMap.get(destination).distance) {
                    distMap.get(destination).distance = newDist.intValue();
                    distMap.get(destination).preVertex = source;

                    if (!inQueueMap.getOrDefault(destination, Boolean.FALSE)) {
                        queue.offer(destination);
                    }
                }
            }
        }

        return distMap;
    }

    public static void main(String args[]) {
        Graph<Integer> graph = new Graph<>();
        graph.addEdge(0, 1, -1);
        graph.addEdge(0, 2, 4);
        graph.addEdge(1, 2, 3);
        graph.addEdge(1, 3, 2);
        graph.addEdge(1, 4, 2);
        graph.addEdge(3, 2, 5);
        graph.addEdge(3, 1, 1);
        // 情况1：包含权重为0的环
        graph.addEdge(4, 3, -3);
        // 情况2：包含负权重的环
//        graph.addEdge(4, 3, -5);

        SPFA<Integer> spfa = new SPFA<>();

        Integer start = 0, end = 3;
        spfa.testSinglePathList(graph, start, end);

        start = 0;
        end = 2;
        spfa.testSinglePathList(graph, start, end);

        start = 3;
        end = 2;
        spfa.testSinglePathList(graph, start, end);
    }
}
